package Util.Map;

import java.io.*;
import java.lang.reflect.ParameterizedType;
import java.lang.reflect.Type;
import java.util.*;
import java.util.function.Consumer;

/**
 * 实现Map: 已经继承AbstractMap还要实现Map接口, 可能的原因有
 * 1, 把Map作为HashMap的直接依赖, 使Map不用关心AbstractMap类的设计, 是一种解耦。
 * 2, Class类的getInterfaces这个方法能够直接获取到Map接口。
 * 3, stackOverflow上有回答, 曾经询问过开发人员Josh Bloch, 就是一个写法上的错误, 并没有深意
 * 实现Cloneable: 想创建对HashMap对象的拷贝, 合法调用clone方法, 必须先实现Cloneable接口, 否则就会抛出CloneNotSupportedException
 */
public class HashMap<K, V> extends AbstractMap<K, V> implements Map<K, V>, Cloneable, Serializable {
    @Serial //jdk11以后,  用于标记与序列相关的字段和方法的注释
    private static final long serialVersionUID = 362498820763181265L;
    /**
     * 默认初始容量 - 必须是2的幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;
    /**
     * 最大容量
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;
    /**
     * 默认负载因子
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * 桶的树化阈值 链表转成红黑树的阈值
     * 在存储数据时, 当链表长度 > 该值时, 则 将链表转换成红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;
    /**
     * 桶的链表还原阈值 红黑树转为链表的阈值
     * 当在扩容时, 在重新计算存储位置后, 当原有的红黑树内数量 < 6时, 则 将红黑树转换成链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;
    /**
     * 最小树形化阈值
     * 当哈希表中的容量 > 该值时, 才允许树形化链表 （即 将链表转换成红黑树）
     * 否则, 若桶内元素太多时, 则直接扩容, 而不是树形化
     * 为了避免进行扩容、树形化选择的冲突, 这个值不能小于 4 * TREEIFY_THRESHOLD
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

    static class Node<K, V> implements Map.Entry<K, V> {
        //用hash方法计算出来的值, 表示的是元素所在桶的位置
        final int hash;
        final K key;
        V value;
        //链表结构, 存储下一个节点的信息
        Node<K, V> next;

        Node(int hash, K key, V value, Node<K, V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        //----除了构造方法外其余方法都被final修饰, 表示不可被子类覆盖----
        @Override
        public final K getKey() {
            return key;
        }

        @Override
        public final V getValue() {
            return value;
        }

        @Override
        public final V setValue(V value) {
            V oldValue = this.value;
            this.value = value;
            return oldValue;
        }

        @Override
        public final boolean equals(Object o) {
            if (o == this) {
                return true;
            }
            return o instanceof Map.Entry<?, ?> e
                    && Objects.equals(key, e.getKey())
                    && Objects.equals(value, e.getValue());
        }

        @Override
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        @Override
        public final String toString() {
            return key + "=" + value;
        }
    }
    /* ---------------- Static utilities -------------- */

    /**
     * 根据Key来定位这个K-V在链表数组HashMap中的位置
     * 计算 key.hashCode() 并将散列的高位散布 (XOR) 到低位
     * 混合原始哈希码的高位和低位, 以此来加大低位的随机性。而且混合后的低位掺杂了高位的部分特征, 也变相保留高位信息
     * exp:
     *  h = hashCode()        : 1111 1111 1111 1111  1111 0000 1110 1010    调用hashCode()
     *  h >>> 16              : 0000 0000 0000 0000  1111 1111 1111 1111
     *  hash = h ^ (h >>> 16) : 1111 1111 1111 1111  0000 1111 0001 0101    移位异或计算hash
     *  -------------------------------------------------------------------------------------
     *  JDK 7 以前的hash方法：
     *  如果 key instanceof String && hashseed == 0 直接调用sun包下的stringHash32方法计算哈希
     *  为了避免哈希冲突的概率, 进行多次扰动, 即多次的右移、异或操作
     */
    static final int hash(Object key){
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    // 目的: 找到一个最小的2^n, 使得 2^n >= number
    // JDK 8 中的实现原理:
    // 对于一个int类型数字(x可能是0, 1)
    // 初始大小X:  0000 01XX XXXX XXXX  XXXX XXXX XXXX XXXX
    // 期望得到Y:  0000 0111 1111 1111  1111 1111 1111 1111
    // 最后得到Z:  0000 1000 0000 0000  0000 0000 0000 0000 即 Z = Y + 1
    // --------------------思路：不断右移 + 或运算--------------------
    // X右移一位:  0000 001X XXXX XXXX  XXXX XXXX XXXX XXXX
    // 与X或运算:  0000 011X XXXX XXXX  XXXX XXXX XXXX XXXX
    // -----------------右移一位再或运算, 有两位变成了1-----------------
    // 右移两位:  0000 0001 1XXX XXXX  XXXX XXXX XXXX XXXX
    // 再或运算:  0000 0111 1XXX XXXX  XXXX XXXX XXXX XXXX
    // 因此右移两次, 高位出现了连续4个1, 因此右移5次, 可以出现2^5(32)个1
    // 不管这个int类型值多大, 都会将其转换, 只是值较小时, 也只是多做几次无意义操作
    static final int tableSizeFor(int cap){
        // JDK 17 的实现
        // Integer.numberOfLeadingZeros(int i)  应用二分查找, 返回无符号整形最高位的非0位之前0的个数
        int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

//        // JDK 8 的实现
//        int n = cap - 1;
//        n |= n >>> 1;
//        n |= n >>> 2;
//        n |= n >>> 4;
//        n |= n >>> 8;
//        n |= n >>> 16;
//        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

    }

    // insanceof  可以理解为是某种类型的实例, 无论是运行时类型, 还是它的父类, 它实现的接口, 他的父类实现的接口, 甚至它的父类的父类的父类实现的接口的父类的父类
    //            总之, 只要在继承链上有这个类型就可以了
    // getClass() 返回运行时的类, 可以简单的理解为它的实际类型, 也就是new它的时候的类型, 但是当匿名对象调用getClass()时返回的是依赖它的对象的运行时类型
    // getGenericInterfaces() 方法返回的是该对象的运行时类型“直接实现”的接口数组(返回的一定是接口, 必然是该类型自己实现的接口，继承过来的不算)
    // ParameterizedType 参数化类型, 即实现了泛型参数的类型, 即带有"<>"
    //                   如果直接用bean对象instanceof ParameterizedType, 结果都是false
    //                   只有用Type对象instanceof ParameterizedType才能得到想要的比较结果
    // getRawType() (前提: instanceof ParameterizedType) 返回声明了这个类型的类或接口, 也就是去掉了泛型参数部分的类型对象
    // getActualTypeArguments()  (前提: instanceof ParameterizedType) getActualTypeArguments()以数组的形式返回泛型参数列表
    // getOwnerType() (前提: instanceof ParameterizedType) 如果该类型是一个内部类/接口，返回它的外部类/接口。如果该类型不是内部类/接口，返回null。
    // -------------------------------------------------------------------
    // 当x的类型为X, 且X直接实现了Comparable接口, 返回x的运行时类型；否则返回null
    static Class<?> comparableClassFor(Object x) {
        if (x instanceof Comparable){
            Class<?> c = x.getClass();
            Type[] ts = c.getGenericInterfaces(), as; ParameterizedType p;
            if(c == String.class) {return c;}
            for (Type t : ts) {
                if((t instanceof ParameterizedType) // 如果该接口用到了泛型
                        && (p = (ParameterizedType) t).getRawType() == Comparable.class // 且调用getRawType方法判断使用了泛型的接口中是否有Comparable接口
                        && (as = p.getActualTypeArguments()) != null
                        && as.length == 1 && as[0] == c){ // 获得泛型中的类,并且判断是否只用了一个泛型, 并且判断该泛型的实现类是否为 x 所属的类
                    return c;
                }

            }
        }
        return null;
    }

    // 如果 x 的类是 kc 则返回 k.compareTo(x)，否则返回 0
    @SuppressWarnings({"rawtypes","unchecked"})
    static int compareComparables(Class<?> kc, Object k, Object x) {
        return (x == null || x.getClass() != kc) ? 0 : ((Comparable) k).compareTo(x);
    }

    /* ---------------- Fields -------------- */
    // 哈希数组(哈希表), 长度总是为2的幂次方
    transient Node<K, V>[] table;
    // 缓存的entrySet
    transient Set<Map.Entry<K, V>> entrySet;
    // HashMap的所有数据的数量
    transient int size;
    // 哈希表的修改次数
    transient int modCount;
    // 负载容量, 扩容的临界值 (容量 * 加载因子) 即 可以存放的最大量
    int threshold;
    /**
     * 哈希表的负载因子
     */
    final float loadFactor;

    /* ---------------- Public operations -------------- */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
        }
        if (initialCapacity > MAXIMUM_CAPACITY) {
            initialCapacity = MAXIMUM_CAPACITY;
        }
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
        }

        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

    public HashMap(Map<? extends K, ? extends V> m){
        this.loadFactor = DEFAULT_LOAD_FACTOR;
        putMapEntries(m, false);
    }

    // evict 英文是驱逐 最初构造此Map时为false，否则为true
    final void putMapEntries(Map<? extends K,? extends V> m, boolean evict) {
        int s = m.size();
        if(s > 0){
            if (table == null) {
                // 将map集合大小除以负载因子h后+1,可以得到HashMap所需的最大负载容量, 也就是阈值, 因为会计算出小数因此+1.0F向上取整
                float ft = ((float) s / loadFactor) + 1.0F;
                int t = ft < MAXIMUM_CAPACITY ? (int) ft : MAXIMUM_CAPACITY;
                // 如果t 大于当前最大负载容量,则进行调整
                // tableSizeFor: 找到一个最小的2^n, 使得 2^n >= t
                if (t > threshold) { threshold = tableSizeFor(t);}
            }else{
                // 由于链表桶的限制, 不能一次全部扩展, 但可以通过while重复加倍来减少总的调整大小工作量
                while (s > threshold && table.length < MAXIMUM_CAPACITY) {
                    resize();
                }
//                // JDK 8 源码
//                if (s > threshold) {resize();}
            }
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean containsKey(Object key) {
        return getNode(key) != null;
    }

    // 返回值为null并不一定表示映射不包含Key, 也可能Key显式映射到null
    @Override
    public V get(Object K){
        Node<K, V> e = getNode(K);
        return e == null ? null : e.value;
    }

    // 为了代码可读性, 稍微重构了一下
    final Node<K,V> getNode(Object key){
        Node<K, V>[] tab = table;
        if(tab == null || tab.length == 0) {return null;}
        int hash = hash(key), n = tab.length;
        Node<K, V> first = table[(n - 1) & hash], e;
        K k;
        if(first != null){
            k = first.key;
            if(first.hash == hash && Objects.equals(k, key)){
                return first;
            }
            e = first.next;
            if (e != null) {
                if (first instanceof TreeNode) {
                    // 红黑树节点
                    // 根据key查找树结构中与之哈希一致的对象
                    return ((TreeNode<K, V>) first).getTreeNode(hash, key);
                }
                // 链表节点
                do {
                    if (e.hash == hash && Objects.equals(e.key, key)) {
                        return e;
                    }
                } while ((e = e.next) != null);

            }
        }
        return null;
//        // 源代码
//        Node<K,V>[] tab; Node<K,V> first, e; int n, hash; K k;
//        if ((tab = table) != null && (n = tab.length) > 0 &&
//                (first = tab[(n - 1) & (hash = hash(key))]) != null) {
//            if (first.hash == hash && // always check first node
//                    ((k = first.key) == key || (key != null && key.equals(k))))
//                return first;
//            if ((e = first.next) != null) {
//                if (first instanceof TreeNode)
//                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//                do {
//                    if (e.hash == hash &&
//                            ((k = e.key) == key || (key != null && key.equals(k))))
//                        return e;
//                } while ((e = e.next) != null);
//            }
//        }
//        return null;
    }

    // 将Key, Value相关联, 如果映射之前包含键的映射, 则旧值将被替换
    // 返回之前的与Key相关联的Value(没有则为空)
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * 实现 Map.put 和相关方法
     * @param onlyIfAbsent 是否只在 当Key为null时 更新关系
     * @param evict 英文是驱逐的意思
     */
    private V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
        Node<K, V>[] tab = table;
        int n;
        if (tab == null || (n = tab.length) == 0) {
            tab = resize();
            n = tab.length;
        }
        // todo 为什么是这样hash
        int i = (n - 1) & hash;
        Node<K, V> p = tab[i];
        if (p == null) {
            tab[i] = newNode(hash, key, value, null);
        }else {
            Node<K, V> e; K k = p.key;
            if (p.hash == hash && (Objects.equals(key, k))) {
                e = p;
            } else if (p instanceof TreeNode) {
                // 当前节点是红黑树节点
                ((TreeNode<K,V>) p ).putTreeVal(this, tab, hash, key, value);
                e = null;
            } else {
                for (int bitCount = 0; ; ++bitCount) {
                    e = p.next;
                    if (e == null) {
                        p.next = newNode(hash, key, value, null);
                        // 重新计算当前链表的长度是不是超出了限制, 超出了之后就将当前链表转换为树
                        if (bitCount >= TREEIFY_THRESHOLD - 1) {
                            // 转换树的时候, 如果当前数组的长度小于MIN_TREEIFY_CAPACITY(默认 64), 会触发扩容
                            treeifyBin(tab, hash);
                        }
                        break;
                    }
                    // 如果当前数据和要插入的数据 哈希 和 key 都一样, 则找到了目标，跳出循环更新键值
                    if (e.hash == hash && Objects.equals(e.key, key)) {
                        break;
                    }
                    // 遍历链表
                    p = e;
                }
            }
            if (e != null) {
                V oldValue = e.getValue();
                // 可以更新K-V键值对的条件
                if (!onlyIfAbsent || oldValue == null) {
                    e.value = value;
                }
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 如果 哈希表(table) 的长度已经超过了 临界值(threshold),
        if (++size > threshold) {
            resize();
        }
        afterNodeInsertion(evict);
        return null;
    }

    /**
     * 初始化或成倍扩容table
     * 如果为 null, 则根据字段阈值中保留的初始容量目标进行分配
     * 否则, 由于我们使用的是 2 次幂扩展, 因此每个 bin 中的元素必须保持在同一索引上, 或者在新表中以 2 的偏移量移动
     */
    final Node<K, V>[] resize(){
        Node<K, V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length, oldThr = threshold;
        int newCap, newThr = 0;
        if(oldCap > 0){
            if (oldCap >= MAXIMUM_CAPACITY) {
                // 无法扩容了
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
                // 当 newCap < 最大容量 且 oldCap >= 默认容量（16）成倍扩容
                newThr = oldThr << 1;
            }
        } else if (oldThr > 0) {
            // oldCap <= 0, 但是oldThr > 0, 说明在初始化容量时设置过阈值(使用的是以下的构造方法),
            // HashMap(int initialCapacity, float loadFactor) 和 HashMap(int initialCapacity)
            // 则 Node<K, V>[] table == null 但是 threshold 是 >= initialCapacity的最小的 2^n
            // 因此, 直接把 oldThr 赋给 newCap
            newCap = oldThr;
        } else {
            // 使用的是无参构造方式, 按默认的初始化规则
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }

        // 初始化 负载容量(threshold) 大小
        if (newThr == 0) {
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);
        }
        threshold = newThr;

        Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];
        table = newTab;
        // 如果 oldTab == null, 直接返回newTable(已被实例化)
        if (oldTab != null) {
            for (int j = 0; j < oldCap; j++) { //遍历table数组
                Node<K,V> e = oldTab[j];
                if (e != null) {
                    oldTab[j] = null;
                    if (e.next == null) {
                        // 单节点
                        // newCap = 2 ^ n, 所以newCap-1 的二进制形式是（1,11,111,1111 ...）这种形式
                        // todo 为什么是这样rehash
                        newTab[e.hash & (newCap - 1)] = e;
                    } else if (e instanceof TreeNode) {
                        // 该节点是一个 treeNode 类型, 形成了红黑树, 说明这个节点下的元素已经树化
                        // 将树中的节点拆分为较低的树和较高的树, 如果太小则取消树化, 变成链表
                        ((TreeNode<K,V>) e).split(this, newTab, j, oldCap);
                    } else{
                        // 链表节点
                        // 索引位只有两种情况:
                        //      一种是扩容后索引位 = 扩容前索引位,
                        //      另一种情况是扩容后索引位 = 扩容前的索引位 + 扩容前的table容量
                        // loHead: 低位首节点 指向重排后仍会处于 原索引位 的节点之间重新链接后的链表的头节点 的指针
                        // loTail: 低位尾节点 指向重排后仍会处于 原索引位 的节点之间重新链接后的链表的尾节点 的指针
                        // hiHead: 高位首节点 指向重排后应该处于 新索引位 的节点之间重新链接后的链表的头节点 的指针
                        // hiTail: 高位尾节点 指向重排后应该处于 新索引位 的节点之间重新链接后的链表的尾节点 的指针
                        Node<K, V> loHead = null, loTail = null;
                        Node<K, V> hiHead = null, hiTail = null;
                        // 遍历链表,
                        do {
                            // 重排后仍会处于 原索引位 的节点, 这些节点之间不一定相邻
                            if ((e.hash & oldCap) == 0) {
                                // 第一次进入该分支: loTail初始为null, 第一次循环结束后头尾节点都指向链表中的第一个节点
                                // 第二次进入该分支: 第一个节点.next = 当前节点, 随后尾指针重新指向了当前的尾节点, 即第二个节点
                                // 循环: loHead指向第一个节点, loTail指向最后一个节点
                                if(loTail == null){
                                    loHead = e;
                                }else{
                                    loTail.next = e;
                                }
                                loTail = e;
                            } else {
                                // 重排后应该处于 新索引位 的节点, 这些节点之间不一定相邻
                                if (hiTail == null) {
                                    hiHead = e;
                                }else{
                                    hiTail.next = e;
                                }
                                hiTail = e;
                            }
                            e = e.next;
                        } while (e != null);
                        // 将两条链表添加到newTab
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

    // 替换给定哈希索引处的 bin 中的所有链接节点, 除非表太小, 在这种情况下改为调整大小
    final void treeifyBin(Node<K, V>[] tab, int hash){
        int n, index; Node<K, V> e;
        // 如果元素数组为空 或者 数组长度小于 树结构化的最小限制, 则直接对数组扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
            resize();
        } else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K, V> head = null, tail = null;
            do {
                // e => p(树节点的e)
                TreeNode<K, V> p = replacementTreeNode(e, null);
                if (tail == null) {
                    head = p;
                } else {
                    // tail -> p
                    // tail <- p
                    // 此时 假设 tmp = tail
                    // tmp -> tail  e(下一次循环中将被转成树节点赋值给p)
                    // tmp <- tail  e(下一次循环中将被转成树节点赋值给p)
                    // 下一次循环中 将建立 tail 与 p(e) 的双向关系
                    // 直到 e = e.next, e == null 结束
                    p.prev = tail;
                    tail.next = p;
                }
                tail = p;
                e = e.next;
            } while (e != null);
            // 到目前为止 只是把Node对象转换成了TreeNode对象, 把单向链表转换成了双向链表
            // 把转换后的双向链表, 替换原来位置上的单向链表
            tab[index] = head;
            if (head != null) {
                // 树化
                head.treeify(tab);
            }
        }

    }

    // 将传入的Map中的所有K-V映射复制到此HashMap中, 键相同时新的映射将替换原有映射
    public void putAll(Map<? extends  K, ? extends  V> m) {
        putMapEntries(m, true);
    }

    // 如果K-V存在, 移除指定K的映射
    public V remove(Object key){
        Node<K, V> e = removeNode(hash(key), key, null, false, true);
        return e == null ? null : e.value;
    }

    /**
     *
     * @param value if matchValue== true 则将value与K-V中的V比对, 否则忽略
     * @param matchValue if true 则仅在值相等时删除
     * @param movable if false 则在移除元素时不移动其他节点(在移除红黑树节点时起作用)
     */
    final Node<K, V> removeNode(int hash, Object key, Object value,
                                boolean matchValue, boolean movable) {
        Node<K, V>[] tab = table; Node<K, V> p; int n, index;
        if (tab != null && (n = tab.length) > 0
                && (p = tab[index = (n - 1) & hash]) != null) {
            // node: 待移除的节点
            Node<K, V> node = null, e = p.next;
            if (p.hash == hash && (Objects.equals(key, p.key))) {
                node = p;
            } else if (e != null) {
                // root不是目标节点, 在红黑树查找
                if (p instanceof TreeNode) {
                    node = ((TreeNode<K, V>) p).getTreeNode(hash, key);
                }else {
                    // 在链表中查找目标节点
                    do {
                        if (e.hash == hash && Objects.equals(key, e.key)) {
                            node = e;
                            break;
                        }
                        p = e;
                        e = e.next;
                    } while (e != null);
                }
            }

            if (node != null && (!matchValue || Objects.equals(value, node.value))) {
                if (node instanceof TreeNode) {
                    ((TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                } else if (node == p) {
                    tab[index] = node.next;
                } else {
                    // 链表逻辑删除
                    p.next = node.next;
                }
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

    public void clear(){
        Node<K, V>[] tab = table;
        modCount++;
        if (tab != null && size > 0) {
            size = 0;
            Arrays.fill(tab, null);
        }
    }

    // 遍历table所有节点的value，意义比对
    public boolean containsValue(Object value) {
        Node<K, V>[] tab = table;
        if (tab != null && size > 0) {
            for (Node<K, V> e : tab) {
                while (e != null) {
                    if (Objects.equals(e.value, value)) {return true;}
                    e = e.next;
                }
            }
        }
        return false;
    }

    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

    final class KeySet extends AbstractSet<K>{
        @Override
        public int size() {return size;}
        @Override
        public Iterator<K> iterator() {return null;}
        public void clear() { HashMap.this.clear();}
        public final boolean contains(Object o) { return containsKey(o); }
        public final boolean remove(Object key) {return removeNode(hash(key), key, null, false, true) != null;}
//        public final Spliterator<K> spliterator() {return new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);}
//        public Object[] toArray(){}
//        public <T> T[] toArray(T[] a) {}
        public final void forEach(Consumer<? super K> action){
            // todo 待分析
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (Node<K,V> e : tab) {
                    for (; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K, V>> es = entrySet;
        return es == null ? (entrySet = new EntrySet()) : es;
    }

    final class EntrySet extends AbstractSet<Map.Entry<K,V>>{
        // todo
        @Override
        public int size() {return size;}
        @Override
        public final Iterator<Entry<K, V>> iterator() {return new EntryIterator();}
        public final void clear(){ HashMap.this.clear(); }

//        @Override
//        public Spliterator<Entry<K, V>> spliterator() {
//            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
//        }
    }

    /* ----------------Cloning and serialization------------------- */

    // 利用 该clone方法 生成的新对象有自己独立的存储空间
    // 新生成的HashMap中的数组属性table数组是开辟了新空间, 但新的HashMap和原来的HashMap所存储的引用类型都是指向的同一存储空间
    @Override
    @SuppressWarnings("unchecked")
    public Object clone(){
        HashMap<K,V> result;
        try {
            // .的优先级高, 之后再强转; 这个result确实是新创建的, 但是里面的属性全是原来的的
            result = (HashMap<K, V>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }
        // result的各个field全部会被设置为默认值 (基本类型归零, 引用类型为null)
        result.reinitialize();
        // 由于putMapEntries的函数逻辑, 会对table成员进行初始化(resize()方法), 并不断往table里添加元素
        result.putMapEntries(this, false);
        return result;
    }

    final float loadFactor() { return loadFactor; }

    final int capacity() {
        return (table != null) ? table.length :
                (threshold > 0) ? threshold :
                        DEFAULT_INITIAL_CAPACITY;
    }

    // HashMap中, 由于Entry的存放位置是根据Key的Hash值来计算, 然后存放到数组中的, 对于同一个Key,在不同的JVM实现中计算得出的Hash值可能是不同的
    // 为了避免这个问题, 将可能会造成数据不一致的元素使用transient关键字修饰, 不序列化的包括: Entry[] table,size,modCount
    // 自己实现writeObject和readObject方法, 保证序列化和反序列化结果的一致性
    @Serial
    private void writeObject(ObjectOutputStream s) throws IOException {
        // todo
    }

    @Serial
    private void readObject(ObjectInputStream s) throws IOException, ClassNotFoundException{
        // todo
    }

    /* -------------------------iterators-------------------------- */

    abstract class HashIterator{
        Node<K, V> current;
        Node<K, V> next;
        // 期望操作数, 用于多线程情况下
        // 如果多个线程同时对 HashMap 进行读写, 那么 expectedModCount 和 modCount 就会不一致, 这时候抛个“快速失败”的异常出来
        int expectedModCount;
        // 当前正在迭代的Node位置索引
        int index;

        HashIterator(){
            expectedModCount = modCount;
            Node<K, V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) {
                // 找到第一个不为空的Node的索引
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {return next != null;}

        final Node<K, V> nextNode(){
            // 多线程情况下实现快速失败
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            if (next == null) {
                throw new NoSuchElementException();
            }
            Node<K, V> e = next;
            Node<K, V>[] t = table;
            current = e;
            if ((next = current.next) == null && t != null) {
                // 找到第一个不为空的Node的索引
                // t.length初始化=16, next不为空时, 继续找, 直到next=t[i]为空时继续循环, 不为空时退出do循环
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        public final void remove(){
            Node<K, V> p = current;
            if (p == null) {
                throw new IllegalStateException();
            }
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            // 这里只是将current指针指向空(便于垃圾回收), current原来指向的地址的数据并没有改变
            current = null;
            removeNode(p.hash, p.key, null, false, false);
            expectedModCount = modCount;
        }
    }

    final class KeyIterator extends HashIterator implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

    final class ValueIterator extends HashIterator implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    final class EntryIterator extends HashIterator implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

    /* -----------------------spliterators------------------------- */


    /* -------------------LinkedHashMap support-------------------- */
    Node<K, V> newNode(int hash, K key, V value, Node<K, V> next) {
        return new Node<>(hash, key, value, next);
    }
    TreeNode<K, V> newTreeNode(int hash, K key, V value, Node<K, V> next) {return new TreeNode<>(hash, key, value, next);}
    // 从 TreeNodes 到普通节点的转换
    Node<K, V> replacementNode(Node<K, V> p, Node<K,V> next){return new Node<>(p.hash, p.key, p.value, next);}
    // 从普通节点到 TreeNodes 的转换
    TreeNode<K, V> replacementTreeNode(Node<K, V> p, Node<K,V> next){return new TreeNode<>(p.hash, p.key, p.value, next);}
    void reinitialize() {
        table = null;
        entrySet = null;
        keySet = null;
        values = null;
        modCount = 0;
        threshold = 0;
        size = 0;
    }
    void afterNodeAccess(Node<K,V> p) { }
    // evict 英文是驱逐的意思 最初构造此Map时为false，否则为true
    void afterNodeInsertion(boolean evict) { }
    void afterNodeRemoval(Node<K,V> p) { }

    /* ------------------------------------------------------------ */

    // HashMap 中的红黑树节点通过 TreeNode 类构造
    // TreeNode extends LinkedHashMap.Entry | LinkedHashMap.Entry extends HashMap.Node
    // 按照按 key 键的散列码由大到小排列 (节点的哈希值排列方式类似于二叉搜索树), 保证了红黑树的有序性
    // 红黑树具有如下特性：
    // 1, 任何一个节点都有颜色，黑色或者红色
    // 2, 根节点是黑色的
    // 3, 父子节点之间不能出现两个连续的红节点
    // 4, 任何一个节点向下遍历到其子孙的叶子节点，所经过的黑节点个数必须相等
    // 5, 空节点被认为是黑色的
    static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V>{
        TreeNode<K, V> parent; // 父节点
        TreeNode<K, V> left; // 左子节点
        TreeNode<K, V> right; // 右子节点
        TreeNode<K, V> prev;
        boolean red; // 是否为红色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

        // 返回当前红黑树的根节点
        TreeNode<K,V> root() {
            for (TreeNode<K,V> r = this, p = r.parent;;) {
                if (p == null) {
                    return r;
                }
                r = p;
            }
        }

        // 将红黑树的root节点移动到tab相对应的索引位置
        // 在树化的过程中，所有的节点的prev、next值均未改变，这里可以简单的理解为对双向链表进行维护
        static <K, V> void moveRootToFront(Node<K, V>[] tab, TreeNode<K, V> root) {
            if(root == null || tab == null){
                return;
            }
            int n = tab.length;
            //root不为空, 数组不为空, 数组容量大于0
            if (n > 0) {
                // 计算索引
                int index = (n - 1) & root.hash;
                // 原链表的头节点
                TreeNode<K, V> first = (TreeNode<K,V>) tab[index];
                //如果头节点和红黑树的root节点不相等, 就需要找到root节点在链表中位置, 并在链表中进行数据交换
                if (root != first) {
                    tab[index] = root;
                    //获得root的前驱节点和后继节点
                    TreeNode<K, V> rp = root.prev;
                    Node<K, V> rn = root.next;

                    // 将 root 节点从链表中逻辑删除
                    // 如果后继节点不为空, 后继节点的前驱节点指向root的前驱节点
                    if (rn != null) {((TreeNode<K, V>) rn).prev = rp;}
                    // 如果前驱节点不为空, 前驱节点的后继节点指向root的后继节点
                    if (rp != null) {rp.next = rn;}

                    // 将root节点移动到链表头部
                    // 如果当前TreeNode不为空, 当前TreeNode的前驱节点指向root
                    if (first != null) {first.prev = root;}
                    //root的后继节点指向当前TreeNode
                    root.next = first;
                    //root的前驱节点指向null
                    root.prev = null;
                }
                assert checkInvariants(root);
            }
        }

        TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            // 获取当前对象
            TreeNode<K,V> p = this;
            do {
                // ph: 当前节点哈希值
                int ph = p.hash, dir; K pk = p.key;
                // 获取当前节点的左子节点，右子节点
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                if (ph > h) {
                    // 当前节点哈希值大于目标哈希值, 递归左子树
                    p = pl;
                } else if (ph < h) {
                    // 当前节点哈希值小于目标哈希值, 递归右子树
                    p = pr;
                } else if (Objects.equals(k, pk)) {
                    // 当前节点哈希值和目标哈希值一样且当前节点的key值等于目标节点key值相等, 返回当前节点
                    return p;
                } else if (pl == null) {
                    //如果左子节点为空，递归右子树
                    p = pr;
                } else if (pr == null) {
                    // 如果右子节点为空，递归左子树
                    p = pl;
                } else if ((kc != null || // 如果当前节点的哈希值等于目标节点的哈希值, 但是当前节点的key值不等于目标节点key值, 则将继续用其他的方法对p节点与k进行比较
                        (kc = comparableClassFor(k)) != null) && //  kc不为空代表k实现了Comparable
                        (dir = compareComparables(kc, k, pk)) != 0) { // dir != 0 表示 k != pk
                    // k < pk 则向左遍历, 否则向右遍历
                    p = (dir < 0) ? pl : pr;
                } else if ((q = pr.find(h, k, kc)) != null) {
                    // key所属类没有实现Comparable
                    // 向p的右边遍历查找，继续递归调用find()
                    return q;
                } else {
                    // key所属类没有实现Comparable
                    // 表示上一步的向右边没找到“pr.find(h, k, kc)”为空, 因此向左遍历
                    p = pl;
                }
            } while (p != null);
            return null;
        }

        // 根据key查找树结构中与之哈希一致的对象
        TreeNode<K,V> getTreeNode(int h, Object k) {
            // root()获取根节点
            // find遍历树结构, 查找对象
            return ((parent != null) ? root() : this).find(h, k, null);
        }

        // 当hashCodes相等且不可比较时, 用一致的插入规则来保持重新平衡之间的等效性
        static int tieBreakOrder(Object a, Object b){
            int d;
            // 对象a和b都不为null则进行比较
            if (a == null || b == null || (d = a.getClass().getName()
                    .compareTo(b.getClass().getName())) == 0) {
                // 如果通过compareTo方法不能解决，则通过native的System.identityHashCode方法
                d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
                        -1 : 1);
            }
            return d;
        }

        // 链表 -> 红黑树, 这里构建的是 红黑树本体, this就是链表节点
        // 最后调用moveRootToFront方法将构建好的红黑树节点的根节点放置在tab数组的桶中
        final void treeify(Node<K, V>[] tab){
            TreeNode<K, V> root = null;
            // x 指向当前节点
            for(TreeNode<K, V> x = this; x != null; x = (TreeNode<K, V>) x.next){
                // 设置当前节点的左右节点为空
                x.left = x.right = null;
                // 如果还没有根节点, 则把当前节点作为根节点
                if (root == null) {
                    x.parent = null;
                    x.red = false;
                    root = x;
                }else{
                    // 已经存在根节点, 组成树节点
                    Class<?> kc = null;
                    for (TreeNode<K, V> p = root; ; ) {
                        // 标识方向 -1: 左;  1: 右
                        int dir;
                        K k = x.key, pk = p.key;
                        int h = x.hash, ph = p.hash;
                        if (ph > h) {
                            dir = -1;
                        } else if (ph < h) {
                            dir = 1;
                        } else if((kc == null && (kc = comparableClassFor(k)) == null) ||
                                (dir = compareComparables(kc, k, pk)) == 0){
                            // 如果走到这个if-else分支, 表示当前节点和目标节点的key的hash值相等, 则将继续用其他的方法对p节点与k进行比较
                            // kc == null 说明kc还没有被赋值, 然后再去调用comparableClassFor方法来判断当前节点的key是否实现了comparable接口
                            // 如果返回的是 null 说明没有实现, 如果实现了, 就会返回Key的class类型, 这里对kc进行了赋值
                            // 如果 comparableClassFor(k) == null, 则当前链表节点的key实现了comparable接口,
                            // 且当前树节点和链表节点是相同Class的实例, 说明没有实现comparable接口, 就不能使用compareComparables方法来判断大小, 进入分支
                            // 如果key实现comparable接口, 则使用该方法并用该方法对 dir 赋值
                            // 但是如果返回的结果是0, 说明compareComparables也没能比较出两者大小, 进入分支使用tieBreakOrder比较
                            dir = tieBreakOrder(k, pk);
                        }

                        // 保存当前树节点
                        TreeNode<K, V> xp = p;
                        p = dir <= 0 ? p.left : p.right;
                        if (p == null) {
                            x.parent = xp;
                            if (dir <= 0) {
                                xp.left = x;
                            }else {
                                xp.right = x;
                            }
                            // 插入新节点后 重新平衡红黑树
                            // todo
                            // root = balanceInsertion(root, x);
                            break;
                        }
                    }
                }
            }
            moveRootToFront(tab, root);
        }

        // 红黑树 -> 链表, 当节点<=6个时会被触发, this就是树节点
        // 这里传入HashMap是为了调用replacementNode()方法，来构建Node节点进而生成链表
        final Node<K,V> untreeify(HashMap<K, V> map) {
            Node<K, V> head = null, tail = null;
            for (Node<K, V> q = this; q != null; q = q.next) {
                // 将树节点构建成链表节点
                Node<K, V> p = map.replacementNode(q, null);
                if (tail == null) {
                    head = p;
                }else {
                    // 进行链表的add
                    tail.next = p;
                }
                // 向后移动
                tail = p;
            }
            return head;
        }

        /**
         * @return TreeNode<K,V> 成功插入返回null，如果找到在红黑树中有key相同的节点，则直接将该节点返回
         */
        final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) {
            // 新数据的key的Class类型
            Class<?> kc = null;
            // 是否调用find方法进行查找, 默认没调用
            boolean searched = false;
            // 查找根节点, 索引位置的头节点并不一定为红黑树的根节点, 所以需要通过调用root()方法来遍历红黑树结构进而找到根节点
            TreeNode<K,V> root = (parent != null) ? root() : this;
            // 将根节点赋值给p节点(当前节点), 从根节点开始遍历红黑树, 从内部终止遍历
            TreeNode<K,V> p = root;
            for (;;){
                // dir: 表示向哪个子树查找, -1左, 1右; ph: 当前树节点的hash; pk: 当前树节点的key
                int dir, ph = p.hash; K pk = p.key;
                if (ph > h) {
                    dir = -1;
                }else if(ph < h){
                    dir = 1;
                } else if(Objects.equals(k, pk)){
                    return p;
                }
                // 如果走到这个if-else分支, 表示当前节点和目标节点的key的hash值相等, 则将继续用其他的方法对p节点与k进行比较
                // kc == null 说明kc还没有被赋值, 需要继续执行后面的代码对kc进行赋值; 如果kc已经被赋值了, 说明已经执行过后面的语句了, 就不用再执行后面comparableClassFor
                // comparableClassFor来判断key是不是实现了comparable接口, 如果返回null 说明key没有实现comparable接口, 整个与运算表达式结果为true, 也就直接进入到if分支内部了
                // 如果key实现comparable接口, 则使用该方法并用该方法对 dir 赋值, 但是如果返回的结果是0, 说明compareComparables也没能比较出两者大小
                else if ((kc == null
                        && (kc = comparableClassFor(k)) == null) ||
                        (dir = compareComparables(kc, k, pk)) == 0) {
                    if(!searched){
                        TreeNode<K,V> q, ch;
                        searched = true;
                        // 从p节点的左节点和右节点分别调用find方法进行查找, 如果查找到目标节点则并终止循环，返回q；
                        if (( (ch = p.left) != null && (q = ch.find(h, k, kc)) != null) ||
                                ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)){
                            return q;
                        }
                    }

                    // 使用定义的一套规则来比较p节点的key和新数据的key大小, 用来决定向左还是向右查找
                    dir = tieBreakOrder(k, pk);// dir<0 则代表 k<pk，则向p左边查找；反之亦然
                }

                // x表示新插入元素构建出来的树节点 xp赋值为x的父节点, 中间变量, 用于下面给x的父节点赋值
                TreeNode<K,V> xp = p;
                // 如果查找结果为null, 说明已经到达了叶子节点, 红黑树插入新节点都会插入到叶子结点的位置, 遍历到了null则代表该位置即为新插入节点x的应该插入的位置
                if ((p = (dir <= 0) ? p.left : p.right) == null){
                    // 走进来代表已经找到x要插入的位置, 只需将x放到该位置即可
                    Node<K,V> xpn = xp.next;
                    // 创建新的节点, 其中x的next节点为xpn, 即将x节点插入xp与xpn之间
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    if (dir <= 0) {
                        xp.left = x;
                    } else {
                        xp.right = x;
                    }
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null){
                        ((TreeNode<K,V>) xpn).prev = x;
                    }
                    // 进行红黑树的插入平衡调整
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

        /**
         * 删除给定的节点, 该节点必须在此调用之前存在
         * 通过重置 prev, next 属性调整双向链表的结构信息
         * 当树中节点过少时, 将树转换成链表
         * @param movable 处理时, 是否移动其他节点
         */
        final void removeTreeNode(HashMap<K, V> map, Node<K, V>[] tab, boolean movable) {
            int n;
            // 数组为空直接返回
            if (tab == null || (n = tab.length) == 0) {return;}
            int index = (n - 1) & hash;
            TreeNode<K,V> first = (TreeNode<K,V>) tab[index], root = first, rl;
            // succ 表示当前要删除的节点的后节点， pred 表示其前节点
            TreeNode<K,V> succ = (TreeNode<K,V>) next, pred = prev;
            if (pred == null) {
                //如果pred节点不存在, 则表示当前节点为根节点, 删除后succ节点成为根节点, 用fist节点标记, 并放在数组上
                tab[index] = first = succ;
            } else {
                //如果pred节点存在, 则将pred节点的后节点指向succ节点
                pred.next = succ;
            }
            if (succ != null) {
                //如果succ节点存在, 则将succ节点的前节点指向pred节点
                succ.prev = pred;
            }

            // 如果当前节点不存在, 直接返回
            if (first == null) {return;}

            //如果root节点的父节点存在, 说明当前root节点不是根节点, 则获取真实根节点
            if (root.parent != null) {root = root.root();}

            // 以上做法是先整理当前节点上的链表关系, 接下来整理红黑树关系
            // 根据root节点和它的左右节点的一些情况, 判断红黑树节点的数量
            if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) {
                //太小了, 转换为链表
                tab[index] = first.untreeify(map);
                return;
            }

            //p 当前节点, pl p节点的左节点, pr p节点的右节点, replacement p节点删除后代替他的节点
            TreeNode<K, V> p = this, pl = p.left, pr = p.right, replacement;
            if (pl != null && pr != null) {
                // 当删除p节点左右节点不为空时, 遍历p的右节点上的左子树(找到replacement节点替换他)
                TreeNode<K, V> s = pr, sl;
                while ((sl = s.left) != null) {
                    s = sl;
                }
                // 得到s s节点是大于p节点的最小节点（替换他的节点）
                // 将s节点和p节点的颜色交换
                boolean c = s.red;
                s.red = p.red;
                p.red = c;

                //sr: s节点的右节点; pp: p节点的父节点
                TreeNode<K, V> sr = s.right;
                TreeNode<K, V> pp = p.parent;
                //如果pr节点就是s节点, 交换他们的关系
                if (s == pr) {
                    p.parent = s;
                    s.right = p;
                } else {
                    //获得s节点的父节点sp
                    TreeNode<K, V> sp = s.parent;
                    //p 与 sp 互相关联
                    if ((p.parent = sp) != null) {
                        if (s == sp.left) {
                            sp.left = p;
                        } else {
                            // todo s是一直向左递归的最终节点，应该不可能进入这个分支
                            sp.right = p;
                        }
                    }
                    //将pr节点变成s节点的右节点, s节点变成pr节点的父节点(s 与 pr 互相关联)
                    s.right = pr;
                    pr.parent = s;
//                    // 源码: 始终为true
//                    if ((s.right = pr) != null) {pr.parent = s;}
                }
                p.left = null;
                //将sr节点的变成p节点的右节点, p节点变成sr节点的父节点(sr 与 p 互相关联)
                if ((p.right = sr) != null) {
                    sr.parent = p;
                }

                //将pl节点变成s节点的左节点, s节点变成pl节点的父节点(s 与 pl 互相关联)
                s.left = pl;
                pl.parent = s;
//                // 源码: 始终为true
//                if ((s.left = pl) != null) {pl.parent = s;}

                //如果pp节点不存在, 那当前s节点就是根节点
                if ((s.parent = pp) == null) {
                    //将root节点指向s节点
                    root = s;
                } else if (p == pp.left) {
                    //如果pp节点存在, 且p节点是pp节点的左节点, 将s节点变成pp节点的左节点
                    pp.left = s;
                } else {
                    //将s节点变成pp节点的右节点
                    pp.right = s;
                }
                // 至此, s节点与p节点交换完毕
                //如果sr节点存在
                if (sr != null) {
                    //将replacement节点变成sr节点
                    replacement = sr;
                } else {
                    //sr节点不存在，将replacement变成p节点
                    replacement = p;
                }
            } else if (pl != null) {
                // 如果pl节点存在, pr节点不存在, 不用交换位置, pl节点成为replacement节点
                replacement = pl;
            } else if (pr != null) {
                //如果pr节点存在, pl节点不存在, 不用交换位置, pr节点成为replacement节点
                replacement = pr;
            } else {//如果都不存在, p节点成为replacement节点
                replacement = p;
            }

            // ------------------------------------------------------ //
            // 以p节点的当前位置性质, 对replacement节点进行操作(覆盖p节点)
            if (p != replacement) {
                // 如果replacement不是p节点 将p节点的父节点pp变成replacement节点的父节点
                TreeNode<K, V> pp = replacement.parent = p.parent;
                //如果pp节点不存在
                if (pp == null) {
                    //replacement节点成为根节点
                    root = replacement;
                } else if (p == pp.left) {
                    //如果pp节点存在，根据p节点在pp节点的位置，设置replacement节点的位置
                    pp.left = replacement;
                } else {
                    pp.right = replacement;
                }
                //将p节点的所有树关系 指空
                p.left = p.right = p.parent = null;
            }

            // 如果p节点是红色, 删除后不影响root节点; 如果是黑色, 找到平衡后的根节点, 并用节点r表示
            TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);

            //如果p节点是replacement节点
            if (replacement == p) {
                // 得到p节点父节点pp
                TreeNode<K, V> pp = p.parent;
                // 将p节点的父节点指空
                p.parent = null;
                if (pp != null) {
                    //如果pp节点存在
                    //根据p节点的位置，将pp节点的对应位置指空
                    if (p == pp.left) {
                        pp.left = null;
                    } else if (p == pp.right) {
                        pp.right = null;
                    }
                }
            }

            //移动新的跟节点到数组上
            if (movable) {
                moveRootToFront(tab, r);
            }
        }


        /**
         * 将红黑中的节点拆分为较高位红黑树和低位红黑树，或者如果树现在太小，则取消树化
         *
         * @param index 当前红黑树所在数组位置
         * @param bit oldCap 旧容量大小
         * @param map 这里将HashMap<K,V> map传入进来是为了调用HashMap类中的replacementNode()方法，用来实现TreeNode转为Node的操作。
         * @param tab HashMap中的数组
         */
        final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit){
            // 获得调用此方法的节点b, 这个节点是存储在数组桶中的TreeNode节点, 也就是红黑树的根节点
            TreeNode<K,V> b = this;
            // 重新链接到 lo 和 hi 列表, 保留顺序
            // 低位树存储索引位置为: "原索引位置"的节点       loHead为链表头节点, loTail为链表尾节点
            // 高位树存储索引位置为: "原索引+oldCap"的节点   hiHead为链表头节点, hiTail为链表尾节点
            TreeNode<K,V> loHead = null, loTail = null;
            TreeNode<K,V> hiHead = null, hiTail = null;
            // lc 低位红黑树的节点数, hc 高位红黑树的节点数
            int lc = 0, hc = 0;
            // 从节点b开始, 遍历整个红黑树节点
            // 这里遍历红黑树是采用链表遍历的方法, 因为TreeNode在维护节点的红黑树结构的同时, 也维护了链表结构
            // 这个循环操作是将所有的节点遍历一篇, 判断出哪些节点需要留在原位置, 哪些节点需要升到高位, 所以这里只需要通过链表方式把所有节点都遍历一遍就可以了。
            for (TreeNode<K,V> e = b, next; e != null; e = next){
                // next赋值为e的下个节点; 到e的next后, 将e的next指向null 以便垃圾收集器回收
                next = (TreeNode<K,V>) e.next;
                e.next = null;
                // bi t二进制表达必定为: 1000..., 所以此处计算只有两个结果, 1或者0
                // 0 TreeNode在新数组的位置是原位置，将节点放入低位树; 1 原位置加上旧数组容量值的位置, 将节点放入高位树
                if ((e.hash & bit) == 0) {
                    // 维护双向链表
                    if ((e.prev = loTail) == null) {
                        loHead = e;
                    } else {
                      loTail.next = e;
                    }
                    loTail = e;
                    ++ lc;
                } else {
                    if ((e.prev = hiTail) == null) {
                        hiHead = e;
                    } else {
                        hiTail.next = e;
                    }
                    hiTail = e;
                    ++hc;
                }
                // 如果低位红黑树存在
                if (loHead != null) {
                    // 如果低位红黑树节点数量小于等于红黑树瓦解阈值6, 将低位红黑树转为链表, 并将头节点放到原位置的桶中
                    if (lc <= UNTREEIFY_THRESHOLD) {
                        tab[index] = loHead.untreeify(map);
                    } else {
                        // 否则将低位红黑树根节点放到数组上
                        tab[index] = loHead;
                        // 高位树不存在则说明原先的节点都在当前红黑树上 则就不需要变化了
                        // 如果高位红黑树存在 则将低位红黑树重新树化 虽然当前已经是红黑树了, 但是节点改变了, 所以要重新进行一遍树化, 梳理节点
                        if (hiHead != null) {
                            loHead.treeify(tab);
                        }
                    }
                }
                // 如果高位红黑树存在
                if (hiHead != null) {
                    if (hc <= UNTREEIFY_THRESHOLD) {
                        tab[index + bit] = hiHead.untreeify(map);
                    } else {
                        tab[index + bit] = hiHead;
                        if (loHead != null) {
                            hiHead.treeify(tab);
                        }
                    }
                }
            }

        }

        /* ----------------------红黑树用法---------------------------- */

        /**
         * 节点左旋
         *            root                                                  root
         *       ......  .......                                      ......  .......
         *    .....             pp(要左旋的节点的父节点)             ......             pp(要左旋的节点的父节点)
         *   ......        p(要左旋的节点)  ......      ---->   .........          r         ..
         *  ........  p.left   r(p.right)     .....                         p      r.right
         *              ... rl(r.left) r.right                       p.left   rl
         */
        static <K,V> TreeNode<K, V> rotateLeft(TreeNode<K,V> root,
                                               TreeNode<K,V> p){
            // r：要左旋节点的右子节点  pp：要左旋节点的父节点  rl：要左旋节点的右孩子的左子节点
            TreeNode<K,V> r, pp, rl;
            // 要左旋的节点 以及 要左旋的节点的右孩子 不为空
            if (p != null && (r = p.right) != null){
                rl = p.right = r.left;
                // 如果r的左孩子不为空，则将其父节点赋值为p
                if (rl != null) {
                    rl.parent = p;
                }
                pp = r.parent = p.parent;
                // 如果父节点为空，说明r已经是顶层节点了，应该作为root并且标为黑色
                if (pp == null) {
                    (root = r).red = false;
                } else if (pp.left == p) {
                    pp.left = r;
                } else {
                    pp.right = r;
                }
                r.left = p;
                p.parent = r;

            }
            return root;
        }

        /**
         * 节点右旋
         *            root                                                  root
         *       ......  .......                                      ......  .......
         *    .....             pp(要右旋的节点的父节点)             ......           pp(要右旋的节点的父节点)
         *   ......        p(要右旋的节点)  ......      ---->   .........         l     ..
         *  ........    l    p.right    .....                           l.left      p
         *        l.left  lr                                                     lr   p.right
         */
        static <K,V> TreeNode<K, V> rotateRight(TreeNode<K,V> root,
                                                TreeNode<K,V> p){
            TreeNode<K,V> l, pp, lr;
            if (p != null && (l = p.left) != null) {
                lr = p.left = l.right;
                if (lr != null) {
                    lr.parent = p;
                }
                pp = l.parent = p.parent;
                if (pp == null) {
                    (root = l).red = false;
                } else if (pp.right == p) {
                    pp.right = l;
                } else {
                    pp.left = l;
                }
                l.right = p;
                p.parent = l;
            }
            return root;
        }

        // 调用该方法，是因为在红黑树插入新节点之后，可能会出现红黑树的失衡，需要重新进行平衡
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x){
            x.red = true;
            /*
             * 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
             * xp：当前节点的父节点 xpp：祖父节点  xppl：左叔父节点 xppr：右叔父节点
             */
            TreeNode<K,V> xp, xpp, xppl, xppr;
            for (;;) {
                // 如果父节点为空、说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
                if ((xp = x.parent) == null) {
                    x.red = false;
                    // 当前节点x即为红黑树的根节点
                    return x;
                }
                // 父节点不为空
                // 如果父节点为黑色, 则无需处理即可维持红黑树性质, 直接返回根节点
                // 因为父节点是黑色, 所以(xpp = xp.parent) == null 始终为false, 这里只是为了对xpp祖父节点进行的复制
                else if (!xp.red || (xpp = xp.parent) == null) {
                    return root;
                }

                // 如果执行到这里，说明新插入节点的父节点是红色
                // 如果父节点是祖父节点的左孩子
                if (xp == (xppl = xpp.left)) {
                    // 如果右叔父节点不为空 且和父节点一样也为红色 出现的情况：上溢LL或上溢LR
                    if ((xppr = xpp.right) != null && xppr.red) {
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        // 运行到这里之后, 就又会进行下一轮的循环, 将祖父节点当做处理的起始节点（当成新的插入节点处理）
                        x = xpp;
                    } else{
                        // 右叔父为空或者为黑色, 即右叔父节点不为红色
                        // 如果插入节点是父节点的右孩子, 即LR插入情况 需要将插入节点作为父节点与祖父节点的父节点
                        // 插入节点的父节点左旋, 祖父节点右旋
                        if (x == xp.right) {
                            // 父节点左旋, 并且将当前节点设置为原父节点，下一步反转父子节点
                            // 此时树结构为 xpp ==> 左xp ==> 右x
                            root = rotateLeft(root, x = xp);
                            // 此时树结构为 xpp ==> 左节点 ==> 左节点(x和xp)
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                            // 此时树结构为 xpp ==> 左节点xp ==> 左节点x
                        }
                        // 如果插入节点是父节点的左节点,只会执行下面的if分支(LL插入)
                        // 如果父节点不为空, 将祖父节点右旋
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }

                    }
                }
                else {
                    // 父节点是祖父节点的右孩子
                    // 如果左叔父节点是红色， 出现情况: 上溢RR 和 上溢RL
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    } else {
                        // 如果左叔父节点不为红色
                        // 如果插入节点是父节点的左孩, 即RL插入情况 需要将插入节点作为父节点与祖父节点的父节点
                        // 插入节点的父节点右旋，祖父节点左旋
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : x.parent;
                        }

                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }

        }

        /**
         * 整个函数是一个循环过程, 可能会经过若干次循环
         * 每次循环体刚开始时, x节点子树的黑节点数, 肯定是比x的兄弟节点子树的黑节点数少1, 这是由removeTreeNode函数来做保证的
         * 在removeTreeNode中只有删除黑色节点才会调用balanceDeletion方法, 导致左右的黑色节点树不一致, x的兄弟节点的黑节点数少1
         * @param x 待删除节点或删除节点的替代节点
         */
        static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x){
            // x 要删除节点在中序遍历时的后继节点 xp：当前节点的父节点 xpl：xp节点的左节点 xpr：xp节点的右节点
            TreeNode<K,V> xp, xpl, xpr;
            for (;;) {
                if (x == null || x == root) {
                    return root;
                }
                // 如果x有父节点, 且x为红色, 直接把x变成黑色, 让x子树的黑节点+1 多次循环可到达此分支
                else if (x.red) {
                    x.red = false;
                    return root;
                }
                xp = x.parent;

                // 到此处, x 必为黑色
                // 如果x是xp的左孩子
                if (x == (xpl = xp.left)) {
                    if ((xpr = xp.right) != null && xpr.red) {
                        // 如果xpr节点不为空, 且xpr节点是红色的
                        // 将xpr设置为黑色, xp设置为红色, 再左旋
                        xpr.red = false;
                        xp.red = true;
                        root = rotateLeft(root, xp);
                        // 重新将xp节点指向x节点的父节点, 并将xpr节点指向xp的右节点
                        xpr = (xp = x.parent) == null ? null : xp.right;
                    }
                    // 若xpr节点不存在，即x的兄弟为空, 则将x节点指向xp节点向上调整, 继续以x父节点调整平衡
                    if (xpr == null) {
                        x = xp;
                    } else {
                        // sl: xpr节点的左节点;sr: xpr节点的右节点
                        TreeNode<K, V> sl = xpr.left, sr = xpr.right;
                        if ((sr == null || !sr.red) &&
                                (sl == null || !sl.red)) {
                            // 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的
                            // 将xpr节点变成红色
                            xpr.red = true;
                            // 则将x节点指向xp节点向上调整
                            x = xp;
                        } else{
                            // sr和sl中存在一个红节点
                            if (sr == null || !sr.red) {
                                // 此处说明sl是红节点,将sl节点设置为黑色
                                sl.red = false;
                                // 将xpr节点设置为红色
                                xpr.red = true;
                                // 右旋
                                root = rotateRight(root, xpr);
                                // 将xpr节点重新指向xp节点的右节点
                                xpr = (xp = x.parent) == null ? null : xp.right;
                            }
                            if (xpr != null) {
                                // 如果xpr节点不为空,让xpr节点与xp节点同色
                                xpr.red = (xp == null) ? false : xp.red;
                                // 当sr节点不为空，将其变成黑色
                                if ((sr = xpr.right) != null) {
                                    sr.red = false;
                                }
                            }
                            // 存在xp节点
                            if (xp != null) {
                                // 将xp节点设置为黑色
                                xp.red = false;
                                // 进行左旋
                                root = rotateLeft(root, xp);
                            }
                            // 将x节点指向root进行下一次循环时跳出
                            x = root;
                        }
                    }
                }
                // 和上边分支的操作是对称的
                // 如果x是xp的右孩子。此分支也完成了对xpl的赋值
                else {
                    // 当x节点是右节点
                    if (xpl != null && xpl.red) {
                        // 当xpl节点存在且为红色
                        // 将xpl变为黑色，xp变为红色
                        xpl.red = false;
                        xp.red = true;
                        // 右旋
                        root = rotateRight(root, xpl);
                        // 将xpl节点重新指向xp节点的左节点
                        xpl = (xp = x.parent) == null ? null : xp.left;
                    } // 如果xpl为黑色，则不会进入到上面的if分支中
                    // 经过上面if，不管它有没有执行，x的兄弟xpl肯定为黑色节点了
                    if (xpl == null) {
                        // 如果xpl节点不存在，则xp节点没有子节点了
                        // 将x节点指向xp节点向上调整
                        x = xp;
                    } else {
                        // sl xpl节点的左节点
                        // sr xpl节点的右节点
                        TreeNode<K, V> sl = xpl.left, sr = xpl.right;
                        // 这种情况说明xpl的孩子里没有红色节点
                        if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
                            // 若sr节点为空或者sr节点是黑色的，且sl节点为空或者sl节点是黑色的
                            // 将xpl节点变成红色
                            xpl.red = true;
                            // 则将x节点指向xp节点向上调整
                            x = xp;
                            // 这种情况说明xpl的孩子里有红色节点
                        } else {
                            // 如果sr为红色，则走此分支；sr其他情况则不会
                            if (sl == null || !sl.red) {
                                // 此处说明sr是红节点,将sr节点设置为黑色
                                sr.red = false;
                                // 将xpr节点设置为红色
                                xpl.red = true;
                                // 左旋
                                root = rotateLeft(root, xpl);
                                // 将xpl节点重新指向xp节点的左节点
                                xpl = (xp = x.parent) == null ? null : xp.left;
                            }
                            // 如果xpl节点存在
                            if (xpl != null) {
                                // xpl最终会旋转到之前xp的位置，并保持xp的颜色
                                xpl.red = xp != null && xp.red;
                                // 如果sl节点存在
                                if ((sl = xpl.left) != null) {
                                    //将sl节点变为黑色
                                    sl.red = false;
                                }
                            }
                            // 如果xp节点存在
                            if (xp != null) {
                                // 将xp节点设置为黑色
                                xp.red = false;
                                // 右旋
                                root = rotateRight(root, xp);
                            }
                            // 将x节点指向root进行下一次循环时跳出
                            x = root;
                        }
                    }
                }
            }
        }

        // 检查红黑树的结构是否正确
        static <K,V> boolean checkInvariants(TreeNode<K,V> t){
            // 获得t节点的父节点, 左子节点, 右子节点, 前节点和后节点
            TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right,
                    tb = t.prev, tn = (TreeNode<K, V>) t.next;
            // 如果前节点不为空, 且前节点的后节点不为t, 返回false
            if (tb != null && tb.next != t) {return false;}
            // 如果后节点不为空, 且后节点的前节点不为t, 返回false
            if (tn != null && tn.prev != t) {return false;}

            // 如果父节点不为空, 且t节点不为父节点的左右子节点, 返回false
            if (tp != null && t != tp.left && t != tp.right) {return false;}
            // 如果左子节点不为空, 且左子节点的父节点不为t 或者 左子节点的hash值大于t节点的hash值, 返回false
            if (tl != null && (tl.parent != t || tl.hash > t.hash)) {return false;}
            // 如果右子节点不为空, 且右子节点的父节点不为t 或者 右子节点的hash值小于t节点的hash值, 返回false
            if (tr != null && (tr.parent != t || tr.hash < t.hash)) {return false;}

            // 如果t节点和他的左右子节点都为红色, 返回false
            if (t.red && tl != null && tl.red && tr != null && tr.red) {
                return false;
            }

            //递归检查左子节点
            if (tl != null && !checkInvariants(tl)) {return false;}
            //递归检查右子节点
            if (tr != null && !checkInvariants(tr)) {return false;}
            return true;
        }
    }

}
